Certain embodiments of the present invention generally relate to systems and methods for creating, storing and accessing roadway network data in a database. Certain embodiments of the present invention generally relate to navigation systems and methods that utilize proximity information to organize blocks of node records.
Route planning systems are well known in the field of navigational instruments. Route planning systems in general define one or more paths through a network of roads between source and destination locations. The path(s) planned by the system may be based on one or more criteria, such as shortest distance, shortest time, user preferences and the like. Several algorithms are known for performing route planning, with such algorithms calculating the route from the source or destination location or from both simultaneously. Conventional planning algorithms operate based on a predefined stored data structure, which includes data indicative of a geographic region containing the source and destination locations.
Presently, cartographic information is charted or mapped by data suppliers as large cartographic data maps. A single cartographic data map may include detailed information for multiple adjoining metropolitan areas and/or detailed maps for large geographic areas and the like. A cartographic data map is typically divided by the data suppliers, by manufactures of the routing devices or by service providers into smaller data structures having a size more conducive to storage on, or wireless transmission to, a navigation or route planning device.
In general, each data structure or data set corresponds to a particular geographic region, such as a city, a county, a state, a country, a continent, etc. Each data structure or data set contains data indicative of features within the associated geographic region. The feature information stored within each data structure may include geographic coordinates (altitude, longitude and latitude), more detailed feature information (county roads, city streets, restaurants, and the like), and higher level feature information (e.g. interstates, state highways, and the like) that collectively define a roadway network. The data structure includes nodal data for each intersection of roads in the roadway network.
Conventional methods for route planning depend on the capabilities of system resources, such as processor speed and the amount and speed of memory. Additionally, many route planning systems require database storage of spatial data. Due to cost considerations, many of these products have tight restrictions on processor performance and on available on-board memory for mass database storage. Hardware restrictions of this nature are particularly troublesome for portable products, such as global positioning devices, involving embedded systems, because such systems require access to spatial (e.g., geographic/cartographic) data for mapping or navigation purposes. The volume of such data is quite large, and the available memory is limited by cost, physical size, and weight considerations. Methods for storing spatial data more efficiently would be useful to either minimize the amount of memory needed, increase the amount of data that may be stored on current systems, or decrease the amount of time necessary to calculate a route.
Conventional route planning systems have experienced certain limitations in organizing and internally transferring data. Generally, route planning systems include at least two memory areas, namely long-term or slow memory that stores large amounts of data for long periods of time and work-space or fast memory that temporarily stores one block of data only while a processor accesses the data. The work-space memory is erased and reloaded each time the processor needs data from the long-term memory that is not in the presently loaded block in the work-space.
Data is loaded into the work-space memory in blocks of predefined size from the long-term memory. The long-term memory is also referred to hereafter as a first memory storage device, and may include a hard drive, CD, disk, and the like. The work-space memory is also referred to hereafter as a second memory, and may include “cache” memory, a direct memory access area, and the like. During operation, the route planner identifies data in the long-term memory, such as nodal data, to which access is desired. In order to access nodal data the route planner must load a data segment of contiguous memory containing the desired nodal data. The data segment is loaded into the work-space memory before reading the content of particular nodal data. The loaded segments are of fixed length based on the size of the work-space memory. The loaded segment is larger than the desired nodal data and thus additional or peripheral nodal data are loaded in the work-space memory with the desired nodal data.
In many system architectures, the cache memory may generally only store one data segment at a time. Hence, only one data segment is accessible to the processor at a time. As the search algorithm advances through potential paths, various nodal data is analyzed. To analyze nodal data, it must be loaded into the cache memory. In each iteration through the search algorithm one or more nodes of interest are identified. If the next nodes of interest are in the presently loaded data segment, the processor simply needs to access the cache memory. However, if the next nodes of interest are not in the loaded data segment, the cache must be “flushed” (erased) and a new data segment loaded from the long-term memory into the cache memory. Data transfers consume time and power. Therefore, it is desirable to flush and reload the cache as few times as possible.
One method proposed for storing spatial data in the long-term memory utilizes an R-Tree index structure. Conventional R-Trees are characterized by a number of bounding rectangles, with a root bounding rectangle representing at least the boundary of the entire spatial region packed and indexed by the R-Tree. Bounding rectangles describe the minimum and maximum latitude and longitude extents of geographical areas. The R-Tree is build based upon a familial relationship, such as parent-child, between bounding rectangles. The bounding rectangles “spread out” below the root, which is the parent of the R-Tree. Each bounding rectangle depending from the root is a child of the root, and may also be a parent to one or more child bounding rectangles. Each child includes information more detailed than the parent, and may also include information that is included in the parent. Thus, bounding rectangles may overlap and identical cartographic data may be stored in multiple locations.
Fractal geometry and space filling curves, such as the Hilbert Space-Filling Curve, have been used to achieve better ordering or an improved clustering of the bounding rectangles to be packed in an R-Tree. The Hilbert Space-Filling Curve accesses two dimensional data and formats it to be stored in a one dimensional space. The Hilbert Space-Filling Curve visits all coordinates in a grid (e.g., rectangle) exactly once, and never crosses itself. Unfortunately, the use of space filling curves, used in connection with the R-Tree format, does not reduce the amount of data to be stored or the need to access multiple bounding rectangles for proximal data.
Conventional navigation devices do not efficiently store data in a manner to minimize the amount of memory required or the time necessary to repeatedly access data from a storage location (e.g., dereferencing a node). Because conventional navigation and route planning devices do not store data in an efficient manner, the devices require additional resources such as memory, and the user must wait a longer period of time for the route to be planned.
Thus, a need exists for improved navigation and route planning devices capable of storing data efficiently, using less storage space and calculating a route faster.